#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct StackNode
{
    int data;
    struct StackNode *next;
} StackNode, *LinkStack;

// 1. 初始化链栈（带头结点）
void InitStack(LinkStack &S)
{
    S = (StackNode *)malloc(sizeof(StackNode)); // 创建头结点
    if (S == NULL)
    {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    S->next = NULL; // 头结点指针域置空
}

// 2. 销毁链栈
void DestroyStack(LinkStack &S)
{
    StackNode *p = S->next; // 从第一个有效结点开始释放
    while (p != NULL)
    {
        StackNode *temp = p;
        p = p->next;
        free(temp);
    }
    free(S); // 释放头结点
    S = NULL;
}

// 3. 压栈操作
bool Push(LinkStack S, int x)
{
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    if (newNode == NULL)
    {
        printf("Memory allocation failed!\n");
        return false;
    }
    newNode->data = x;
    newNode->next = S->next; // 新结点指向原第一个结点
    S->next = newNode;       // 头结点指向新结点
    return true;
}

// 4. 出栈操作
bool Pop(LinkStack S, int &x)
{
    if (S->next == NULL)
    { // 栈空判断
        printf("Stack is empty!\n");
        return false;
    }
    StackNode *temp = S->next;
    x = temp->data;
    S->next = temp->next; // 头结点指向新的第一个结点
    free(temp);           // 释放原第一个结点
    return true;
}

// 5. 获取栈顶元素
bool GetTop(LinkStack S, int &x)
{
    if (S->next == NULL)
    { // 栈空判断
        printf("Stack is empty!\n");
        return false;
    }
    x = S->next->data;
    return true;
}

// 6. 获取栈底元素
bool GetBottom(LinkStack S, int &x)
{
    if (S->next == NULL)
    { // 栈空判断
        printf("Stack is empty!\n");
        return false;
    }
    StackNode *p = S->next;
    while (p->next != NULL)
    { // 遍历到最后一个结点
        p = p->next;
    }
    x = p->data;
    return true;
}

// 打印栈内容（从栈顶到栈底）
void PrintStack(LinkStack S)
{
    if (S->next == NULL)
    {
        printf("Stack is empty\n");
        return;
    }

    printf("Stack [top->bottom]: ");
    StackNode *p = S->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main()
{
    LinkStack S;
    InitStack(S); // 初始化链栈

    // 压栈操作
    Push(S, 10);
    Push(S, 20);
    Push(S, 30);
    PrintStack(S); // Stack [top->bottom]: 30 20 10

    // 获取栈顶和栈底
    int top, bottom;
    GetTop(S, top);
    GetBottom(S, bottom);
    printf("Top: %d, Bottom: %d\n", top, bottom); // Top: 30, Bottom: 10

    // 出栈操作
    int popped;
    Pop(S, popped);
    printf("Popped: %d\n", popped); // Popped: 30
    PrintStack(S);                  // Stack [top->bottom]: 20 10

    // 栈空测试
    printf("Testing stack empty:\n");
    while (Pop(S, popped))
    {
        printf("Popped: %d\n", popped);
    }

    // 获取空栈元素测试
    GetTop(S, top);
    GetBottom(S, bottom);

    DestroyStack(S); // 销毁链栈
    return 0;
}